HomeArchivesTagsAbout

从Word Ladder II学习深搜&广搜

Leetcode上有这样一道题：Q126. Word Ladder II

这是一道Hard难度的题目，通过率也不高，但是很好的结合了深度优先搜索和广度优先搜索，我希望用这道题目来总结一下深搜&广搜的思想。

  • 测试无序列表

  • 测试无序列表

  • 测试无序列表

题目描述

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1、Only one letter can be changed at a time

2、Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

Return

[
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
]

Note:

Return an empty list if there is no such transformation sequence.

All words have the same length.

All words contain only lowercase alphabetic characters.

You may assume no duplicates in the word list.

You may assume beginWord and endWord are non-empty and are not the same.

解题思路

  1. 测试有序列表

  2. 测试有序列表

  3. 测试有序列表

First Header Second Header Third Header
Left Center Right
Left Center Right

既然本文的想法就是希望通过此题来总结深搜&广搜，所以我们的思路也自然是将深搜和广搜结合起来解题，当然，能够结合起来也是有原因的，我们需要知道深搜和广搜，分别适合哪种情况的求解。

深度优先搜索：适用于需要求解出所有可能解的问题，在到达问题界限之前会一直递归下去。

广度优先搜索：层级遍历，适用于那些最小或最短问题的求解，核心思想是通过队列或优先队列保存状态，优先选择看似最优的状态进行扩展，以达到最先扩展到目标节点的目的。

在本题中，我们既要求得所有的转移序列，又要得到其中最短的序列的集合。

在我最初的解法中，只使用了深度优先搜索，求得所有的转移序列，然后在其中寻找最短的，但是这样的解法，会造成深度遍历的冗余，和后续没有必要的筛选工作，因此也TLE了。

那么何不先进行广度优先搜索，构造出图和最短路径，然后再进行深度优先搜索，在图和最短路径的约束下递归得到所有的可能呢？

入口函数

于是，我们可以这样完成入口函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
	// Just means wordList, but as a set
	HashSet<String> dict = new HashSet<String>(wordList);
	List<List<String>> res = new ArrayList<List<String>>();
	HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>(); // Neighbor for every node
	HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
	ArrayList<String> solution = new ArrayList<String>();
	dict.add(start);
	solution.add(start);
	bfs(start, end, dict, nodeNeighbors, distance);
	dfs(start, end, dict, nodeNeighbors, distance, solution, res);
	return res;
}

以一个HashSet:dict来保存wordList。

最后返回的结果用List:res保存。

以一个HashMap:nodeNeighbors保存每一个节点的邻接点，以构成图，在bfs中求出来。

以一个HashMap:distance保存到每一个节点的最短路径，在bfs中求出来。

bfs

bfs的解题方法一般是如下的：

1
2
3
4
5
6
7
8
9
10
11
12
13
BFS()
{
  输入起始点；
  初始化所有顶点标记；
  初始化一个队列queue并将起始点放入队列；

  while（queue不为空）
  {

    从队列中删除一个顶点s并标记为已遍历； //表示遍历了s
    将s邻接的所有还没遍历的点加入队列；
  }
}

于是代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
	// 初始化已经在入口函数中完成了。
	for (String str : dict) {
		nodeNeighbors.put(str, new ArrayList<String>());
	}

	Queue<String> queue = new LinkedList<String>();
	queue.offer(start);
	distance.put(start, 0);

	while (!queue.isEmpty()) {
		int count = queue.size();
		boolean foundEnd = false;
		for (int i = 0; i < count; i++) {
			String cur = queue.poll();
			int curDistance = distance.get(cur);
			ArrayList<String> neighbors = getNeighbors(cur, dict);

			for (String neighbor : neighbors) {
				nodeNeighbors.get(cur).add(neighbor);
				if (!distance.containsKey(neighbor)) { //Check if visited
					distance.put(neighbor, curDistance + 1);
					if (end.equals(neighbor))
						foundEnd = true;
					else
						queue.offer(neighbor);
					}
				}
		}

		if (foundEnd)
			break;
	}
}

// Find all next level nodes
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
	ArrayList<String> res = new ArrayList<String>();
	char chs[] = node.toCharArray();

	for (char ch = 'a'; ch <= 'z'; ch++) {
		for (int i = 0; i < chs.length; i++) {
			if (chs[i] == ch) continue;
			char old_ch = chs[i];
			chs[i] = ch;
			if (dict.contains(String.valueOf(chs))) {
				res.add(String.valueOf(chs));
			}
			chs[i] = old_ch;
		}
	}
	return res;
}

如此我们使用bfs的目的就达到了，我们利用层级遍历构造了nodeNeighbors，以此作为dfs中需要用到的图，并构造了到达每个节点的最短路径的distance。

从文

dfs

dfs的解题方法一般是如下的：

1
2
3
4
5
6
7
8
9
10
11
12
13
DFS() {
  if(到达目标递归深度) {
    判断当前状态是否为解？->添加当前状态到解集合
    return
  }
  for(i in 所有可能情况) {
    if(i还未进行搜索) {
      标记i已搜索
      dfs()
      还原现场（标记i未搜索）
    }
  }
}

dfs需要注意的点是：参数记录的状态、过滤掉不可能的状态、状态的保存和还原。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// DFS: output all paths with the shortest distance
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
	if (end.equals(cur)) {
		res.add(new ArrayList<String>(solution));
		return;
	}

	for (String next : nodeNeighbors.get(cur)) {
		if (distance.get(next) == distance.get(cur) + 1) {
			solution.add(next);
			dfs(next, end, dict, nodeNeighbors, distance, solution, res);
			solution.remove(solution.size() - 1);
		}
	}
}

需要注意的是，此处的判断：if (distance.get(next) == distance.get(cur) + 1)，用来过滤掉非最短路径的情况，当前者小于后者时，这样的路径不是最短的。